package com.zjsru.leetcode75.level1.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: cookLee
 * @Date: 2023-12-13
 * 叶子相似的树
 */
public class LeafSimilar {
    /**
     * 主
     * \
     * 输入：root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
     * 输出：true
     * \
     * 输入：root1 = [1,2,3], root2 = [1,3,2]
     * 输出：false
     * \
     * @param args args
     */
    public static void main(String[] args) {
        TreeNode root1 = new TreeNode(3, new TreeNode(5, new TreeNode(6, null, null), new TreeNode(2, new TreeNode(7, null, null), new TreeNode(4, null, null))), new TreeNode(1, new TreeNode(9, null, null), new TreeNode(8, null, null)));
        TreeNode root2 = new TreeNode(3, new TreeNode(5, new TreeNode(6, null, null), new TreeNode(7, null, null)), new TreeNode(1, new TreeNode(4, null, null), new TreeNode(2, new TreeNode(9,null,null), new TreeNode(8,null,null))));
        LeafSimilar leafSimilar= new LeafSimilar();
        System.out.println(leafSimilar.leafSimilar(root1, root2));
    }

    /**
     * 叶相似 bfs
     *
     * @param root1 root1
     * @param root2 root2
     * @return boolean
     */
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        //通过定义两个列表存储每颗树的叶子节点来比较
        List<Integer> leaf1 = new ArrayList<>();
        if(root1 != null){
            this.bfs(root1,leaf1);
        }
        List<Integer> leaf2 = new ArrayList<>();
        if(root2 != null){
            this.bfs(root2,leaf2);
        }
        return leaf1.equals(leaf2);
    }

    /**
     * bfs
     * 深度优先搜索助手类
     *
     * @param root 根
     * @param leaf 叶子
     */
    private void bfs(TreeNode root, List<Integer> leaf) {
        //左右都不存在子节点就加入到列表中
        if (root.left == null && root.right == null) {
            leaf.add(root.val);
        } else {
            if (root.left != null) {
                this.bfs(root.left, leaf);
            }
            if (root.right != null) {
                this.bfs(root.right, leaf);
            }
        }
    }

}
